#include "stdio.h"
#include "stdlib.h"

typedef char VertexType; // 顶点类型用户可自定义
typedef int EdgeType; // 边上的权值类型用户可自定义
# define MAXVEX 100 // 最大顶点数，可自定义
# define INFINITY 65535 // 用65535表示无穷
typedef struct {
    VertexType vex[MAXVEX]; // 一维数组存放顶点集
    EdgeType arc[MAXVEX][MAXVEX]; // 二维数组存放边，邻接矩阵
    int numNodes, numEdges; // 图中当前顶点数和边数
}MGraph;

void createMGraph(MGraph *G) {
    int i, j, k, w;
    printf("输入顶点数和边数：\n");
    scanf("%d,%d", &G->numNodes, &G->numEdges);
    // 初始化顶点，建立顶点表
    for (i = 0; i < G->numNodes; i++) {
        scanf(&G->vex[i]);
    }
    // 邻接矩阵初始化
    for (i = 0; i < G->numNodes; i++) {
        for(j = 0; j < G->numNodes; j++) {
            // 默认所有均为无穷值
            G->arc[i][j] = INFINITY;
        }
    }
    // 读取边数，建立边表
    for (k = 0; k < G->numEdges; k++) {
        printf("输入边（vi, vj）上的下标i，下标j，和权w\n");
        scanf("%d,%d,%d", &i, &j, &w);
        // 无向图对称
        G->arc[i][j] = w;
        G->arc[j][i] = w;
    }
}


typedef char VertexType; // 顶点类型用户可自定义
typedef int EdgeType; // 边上的权值类型用户可自定义

// 边表结点
typedef struct EdgeNode{
    // 邻接点域，存储该顶点对应的下标
    int adjvex;
    // 用于存储权值，对于非网图可不需要
    EdgeType info;
    // 链域，指向下一个邻接点
    struct EdgeNode *next;
}EdgeNode;

// 顶点表结点
typedef struct VertexNode {
    // 顶点域，存储顶点信息
    VertexType data;
    // 边表头指针
    EdgeNode *firstEdge;
}VertexNode, AdjList[MAXVEX];

typedef struct {
    AdjList adjList;
    // 当前顶点数和边数
    int numNodes, numEdges;
}GraphAdjList;

void createGraphAdjList(GraphAdjList *G) {
    int i,j,k;
    EdgeNode *e;
    printf("输入顶点数和边数：\n");
    scanf("%d,%d", &G->numNodes, &G->numEdges);
    // 读取顶点信息，建立顶点表
    for (i = 0; i < G->numNodes; i++) {
        // 顶点信息输入
        scanf(&G->adjList[i].data);
        // 边表初始化置为空
        G->adjList[i].firstEdge = NULL;
    }
    // 建立边表
    for (k = 0; k < G->numEdges; k++) {
        printf("输入边（vi,vj）上的顶点序号：\n");
        scanf("%d,%d", &i,&j);
        // 申请内存空间，生成边结点
        e = (EdgeNode *)malloc(sizeof (EdgeNode));
        // 邻接点序号信息
        e->adjvex = j;
        // 将新建结点的指针指向当前顶点指向的结点（类似头插法）
        e->next = G->adjList[i].firstEdge;
        // 将当前顶点指向新建的结点
        G->adjList[i].firstEdge = e;
        // 因为是无向图，所以一条边对应的是两个顶点，故操作与上述基本类似
        e = (EdgeNode *)malloc(sizeof (EdgeNode));
        e->adjvex = i;
        e->next = G->adjList[j].firstEdge;
        G->adjList[j].firstEdge = e;
    }
}
